COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00011 ENDMK
C⊗;
\input macro[1,mps]
% Make \leftarrow and \rightarrow binary, not relations
\mathchardef\leftarrow="2220
\mathchardef\rightarrow="2221
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm B01.tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, May 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Composition of Machines and Programs} [will replace A65]
\smallskip
Let $M↓1$ and $M↓2$ be transducers, each with its own memory devices.  Let
$P↓1$ and $P↓2$ be programs for the transducers, with transfer relations
$\tau ↓1$ and $\tau ↓2$.  We assume $P↓2$ uses standardized input.  Then we
can combine $P↓1$ and $P↓2$ into a program called $P↓1 \circ P↓2$ for a
single transducer that uses the combined memory devices of $M↓1$ and
$M↓2$ to obtain the transfer function $\tau ↓1 \circ \tau ↓2$.
\smallskip
For simplicity, assume that the write operations of $P↓1$, and the 
read operations of $P↓2$, are in separate instructions.  In outline,
$P↓1 \circ P↓2$ works by performing operations of $P↓1$ until $P↓1$
writes a character, then operations of $P↓2$ until $P↓2$ reads that
character, continuing to alternate between $P↓1$ and $P↓2$.  When $P↓1$
halts, operations of $P↓2$ are performed, including an end-of-file
operation, until $P↓2$ halts.  A finite store, called a buffer, is
used to hold information about output of $P↓1$ not yet processed by 
$P↓2$.
\smallskip
Suppose $x \tau ↓1 \tau ↓2 z$.  Then there is some string
$y = a↓1 a↓2 \cdot\cdot \cdot a↓n$ for which $x \tau↓1 y$ and
$y \tau↓2 z$.  There is a computation of $P↓1$ that accepts $x$ and
writes $y$; it can be segmented at the steps that write the
characters of $y$, into
$$c↓1 w↓1 c↓2 w↓2 \ldots c↓n w↓n c↓{n+1}$$
where $c↓i$ writes nothing and $w↓i$ only writes $a↓i$.  There is
a computation of $P↓2$ that accepts $y$ and writes $z$; it can
be segmented at the steps that scan the characters of $y$, into
$$d↓1 s↓1 d↓2 s↓2 \ldots d↓n s↓n d↓{n+1}$$
where $d↓1$ scans no input, $s↓i$ only scans $a↓i$, and $d↓{n+1}$ performs 
eof.  We construct $P↓1 \circ P↓2$ to have a computation
$$c↓1 w'↓1 d↓1 s'↓1 \ldots c↓n w'↓n d↓n s'↓n c↓{n+1} d↓{n+1}$$
where $w'$ and $s'$ omit the write and scan operations in favor of buffer
operations.
\smallskip
Suppose $M↓1$ is $\langle {\rm control↓1, input, memory↓1, output}\rangle$
and $M↓2$ is $\langle {\rm control↓2, input, memory↓2, output} \rangle$. Then
$M↓1 \circ M↓2$ is $\langle {\rm control↓1, input, memory↓1, buffer,
control↓2, memory↓2, output} \rangle$.  Initial states are those of
$M↓1$ and $M↓2$; the initial state of the buffer is $\Lambda$.
\smallskip
For each non-writing instruction $\langle i\rightarrow j, f, g, {\rm noop} 
\rangle$
of $P↓1$, let $P↓1 \circ P↓2$ contain the instruction $\langle i→j, f, g, \Lambda
→ \Lambda, {\rm noop, noop, noop}\rangle$.  These
perform steps of $c↓i$ so long as the buffer is empty.  For each
writing instruction $\langle i \rightarrow j, {\rm noop, noop, write\ a} 
\rangle$
of $P↓1$, there is an instruction $\langle i→j, {\rm noop, noop}, \Lambda
→a, {\rm noop, noop, noop} \rangle$ of $P↓1 \circ P↓2$.  These, from which
the $w'↓i$ are chosen, put $a$ into the buffer to start performing steps
of $P↓2$.
\smallskip
For each non-input instruction $\langle i→j, {\rm noop}, g, h \rangle$ of
$P↓2$, there is an instruction $\langle {\rm noop}, \allowbreak {\rm noop},
\allowbreak {\rm noop}, \allowbreak {\rm buffer}
\not= \Lambda, i→j, g, h \rangle$ of $P↓1 \circ P↓2$. These perform the steps of
$d↓i$.  For each instruction $\langle i→j, {\rm scan\ a, noop, noop} \rangle$
of $P↓2$, there is an instruction $\langle {\rm noop, noop, noop}, a→\Lambda,
i→j, {\rm noop, noop} \rangle$ of $P↓1 \circ P↓2$.  These, from which the
$s↓i$ are chosen, remove $a$ from the buffer to start performing
steps of $P↓1$.
\smallskip
Let $f, g$, and $h$ be tests of $M↓1$, that test for accepting states
of control, input, and storage.  Then there is an instruction
$\langle f, g, h, \Lambda → e, {\rm noop, noop, noop} \rangle$ that
comes into play when the computation of $P↓1$ is completed (all of
$y$ has passed through the buffer) and $P↓2$ has consumed all of
$y$, leaving the buffer empty.  By setting the buffer to $e$, it
enables the equivalent of eof tests.
\smallskip
Let $\langle i→j, {\rm eof, noop, noop} \rangle$ be an instruction of
$P↓2$.  Then there is an instruction $\langle {\rm noop}, \allowbreak
{\rm noop}, \allowbreak {\rm noop},
\allowbreak e→e, i→j, {\rm noop, noop} \rangle$ of $P↓1 \circ P↓2$ that replaces 
the end-of-file test in $d↓{n+1}$.  The state $e$ is the accepting state
of the buffer.
\smallskip
In the usual way, the two finite control devices and the buffer may be
combined into a single control device, yielding a composite machine with 
devices $\langle {\rm control, input, memory↓1, memory↓2, output} \rangle$.
\smallskip
It should be clear that $P↓1 \circ P↓2$ is deterministic if $P↓1$
and $P↓2$ are, and computes a total function if $P↓1$ and $P↓2$ do.
Thanks to Richard Beigel for the idea of the construction.
\bye